<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8" />
   
  <meta name="keywords" content="Java Python" />
   
  <meta name="description" content="From Zero to Hero" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    JDK1.8源码-07-java.util.HashMap |  朱酱酱的学习博客
  </title>
  <meta name="generator" content="hexo-theme-yilia-plus">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/css/style.css">

  
<script src="/js/pace.min.js"></script>


  

  

<link rel="alternate" href="/atom.xml" title="朱酱酱的学习博客" type="application/atom+xml">
</head>

</html>

<body>
  <div id="app">
    <main class="content">
      <section class="outer">
  <article id="post-jdk_SourceCode/JDK1.8-07-HashMap" class="article article-type-post" itemscope
  itemprop="blogPost" data-scroll-reveal>

  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  JDK1.8源码-07-java.util.HashMap
</h1>
  

    </header>
    

    
    <div class="article-meta">
      <a href="/2020/05/03/jdk_SourceCode/JDK1.8-07-HashMap/" class="article-date">
  <time datetime="2020-05-03T07:52:53.000Z" itemprop="datePublished">2020-05-03</time>
</a>
      
      
      
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">8.8k字</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">36分钟</span>
        </span>
    </span>
</div>

      
    </div>
    

    
    
    <div class="tocbot"></div>





    

    <div class="article-entry" itemprop="articleBody">
      


      

      
      <h1 id="JDK1-8源码-08-java-util-HashMap"><a href="#JDK1-8源码-08-java-util-HashMap" class="headerlink" title="JDK1.8源码-08-java.util.HashMap"></a>JDK1.8源码-08-java.util.HashMap</h1><p>本篇来介绍在 JDK1.8 中 HashMap 的源码实现，这也是最常用的一个集合。但是在介绍 HashMap 之前，我们先介绍什么是 Hash表。</p>
<p><strong>B站很好的HashMap视频</strong>： <a href="https://www.bilibili.com/video/BV1LJ411W7dP" target="_blank" rel="noopener">https://www.bilibili.com/video/BV1LJ411W7dP</a></p>
<a id="more"></a>



<h2 id="1-哈希表"><a href="#1-哈希表" class="headerlink" title="1. 哈希表"></a>1. 哈希表</h2><p>Hash表也被称为散列表，也有直接译为哈希表，Hash表是一个根据关键字值（key-value）而直接进行访问的数据结构。</p>
<p>也就是说它通过把关键码映射到表中一个位置来访问记录，以此来加快查找的速度。</p>
<p><strong>在链表，数组等数据结构中</strong>，查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间复杂度，但对于哈希表来说，只是O(1)的时间复杂度。</p>
<p><strong>比如对于，ArrayList集合和LinkedList来说，如果要查找两个集合中的某个元素，通常是通过遍历整个集合，需要O(N)的时间复杂度。</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200419/212353731.png" alt="mark"></p>
<p>如果是哈希表的话，它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个<strong>映射函数叫做散列函数</strong>，<strong>存放记录的数组叫做散列表</strong>。只需要O(1)的时间复杂度。</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200419/212747630.png" alt="mark"></p>
<p>①、存放在哈希表中的数据是key-value 键值对，比如存放哈希表的数据为:</p>
<p>　　<strong>{Key1-Value1,Key2-Value2,Key3-Value3,Key4-Value4,Key5-Value5,Key6-Value6}</strong></p>
<p>如果我们想查找是否存在键值对 Key3-Value3，首先通过 Key3 经过散列函数，得到值 k3，然后通过 k3 和散列表对应的值找到是 Value3。</p>
<p>②、当然也有可能存放哈希表的值只是 Value1,Value2,Value3这种类型：</p>
<p><strong>{Value1,Value2,Value3,Value4,Value5,Value6}</strong></p>
<p>这时候我们<strong>假设Value1是等于Key1的</strong>，也就是{Value1-Value1,Value2-Value2,Value3-Value3,Value4-Value4,Value5-Value5,Value6-Value6}。可以将Value1经过散列函数转换成与散列表对应的值。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">大家都用过汉语字典吧，汉语字典的优点是我们可以通过前面的拼音目录快速定位到所要查找的汉字。当给定我们某个汉字时，大脑会自动将汉字转换成拼音（如果我们认识，不认识可以通过偏旁部首），这个转换的过程我们可以看成是一个散列函数，之后在根据转换得到的拼音找到该字所在的页码，从而找到该汉字。</span><br></pre></td></tr></table></figure>

<p>汉语字典是哈希表的典型实现，但是我们仔细思考，会发现这样几个问题？</p>
<p><strong>①、为什么要有散列函数？</strong></p>
<p>对于第一个问题，<strong>散列函数的存在能够帮助我们更快的确定key和value的映射关系，</strong>试想一下，如果没有汉字和拼音的转换规则（或者汉字和偏旁部首的），给你一个汉字，你该如何从字典中找到该汉字？我想除了遍历整部字典，你没有什么更好的办法。</p>
<p><strong>②、多个 key 通过散列函数会得到相同的值，这时候怎么办？</strong></p>
<p>对于第二个问题，多个key通过散列函数得到相同的值，这其实也就是<strong>哈希表最大的问题–冲突</strong>，比如同音字汉字，我们得到的拼音就是相同的。那么我们该如何在字典中存放同音字汉字呢？有两种做法：</p>
<ul>
<li><p><strong>第一种：开放地址法</strong></p>
<ul>
<li>当我们遇到冲突了，这时候通过<strong>另一种函数再计算一遍，得到相应的映射关系。</strong></li>
<li>比如对于汉语字典，一个字 “余”，拼音是“yu”，我们将其放在页码为567(假设在该位置)，这时候又来了一个汉字“于”，拼音也是“yu”，那么这时候我们要是按照转换规则，也得将其放在页码为567的位置，但是我们发现这个页码已经被占用了，这时候怎么办？我们可以在通过另一种函数，得到的值加1。那么汉字”于”就会被放在576+1=577的位置。</li>
</ul>
</li>
</ul>
<ul>
<li><p><strong>第二种：链地址法</strong></p>
<ul>
<li>我们可以将字典的每一页都看成是一个子数组或者子链表，<strong>当遇到冲突了，直接往当前页码的子数组或者子链表填充即可。</strong></li>
<li>那么我们进行同音字查找的时候，可能需要遍历其子数组或者子链表。如下图所示：</li>
</ul>
</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200419/213509026.png" alt="mark"></p>
<p>小结：</p>
<ul>
<li>对于开放地址法，可能会遇到二次冲突，三次冲突，所以需要良好的散列函数，分布的越均匀越好。</li>
<li>对于链地址法，虽然不会有二次冲突，但是如果一次冲突很多，那么会造成子数组或者子链表。</li>
</ul>
<h2 id="2-什么是HashMap"><a href="#2-什么是HashMap" class="headerlink" title="2. 什么是HashMap?"></a>2. 什么是HashMap?</h2><p>听名字就知道，HashMap 是一个利用哈希表原理来存储元素的集合。遇到冲突时，<strong>HashMap 是采用的链地址法来解决，</strong></p>
<ul>
<li><p><strong>在JDK1.7中，HashMap是由数组+链表构成的。</strong></p>
</li>
<li><p><strong>但是在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层的数据结构，结构变复杂了，但是效率也更高效。</strong></p>
</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200420/090843192.png" alt="mark"></p>
<h2 id="3-定义"><a href="#3-定义" class="headerlink" title="3.  定义"></a>3.  定义</h2><p>HashMap 是一个散列表，它存储的内容是键值对(key-value)映射，<strong>而且 key 和 value 都可以为 null。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">HashMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">implements</span> <span class="title">Map</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;, <span class="title">Cloneable</span>, <span class="title">Serializable</span> </span>&#123;</span><br></pre></td></tr></table></figure>

<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200420/091324715.png" alt="mark"></p>
<p>首先该类实现了一个Map接口，该接口定义的一组键和值对映射的通用操作。存储的一组成对的key-value对象，提供key到value的映射。</p>
<p><strong>Map中的key不要求有序,不允许重复。</strong></p>
<p><strong>Map中的value同样不要求有序,但可以重复。</strong></p>
<p>但是我们发现该接口方法有很多，我们设计某个键值对的集合有时候并不想实现那么多方法，那该怎么办？</p>
<p><strong>JDK 还为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。</strong></p>
<p><strong>但是我们发现 HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？后面我们会讲的 LinkedHashSet 集合也有这样的写法。</strong></p>
<p>毕竟 JDK 经过这么多年的发展维护，起初也是认为这样是有具体的作用的，后来找了很多资料，发现这其实完全没有任何作用。[说明链接][<a href="https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete]" target="_blank" rel="noopener">https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete]</a></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。</span><br></pre></td></tr></table></figure>

<p>HashMap集合还实现了Cloneable接口和Serializable接口，分别用来对对象进行克隆和序列化。</p>
<h2 id="4-字段属性"><a href="#4-字段属性" class="headerlink" title="4. 字段属性"></a>4. 字段属性</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//序列化和反序列化时，通过该字段进行版本一致性验证</span></span><br><span class="line">   <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">long</span> serialVersionUID = <span class="number">362498820763181265L</span>;</span><br><span class="line">   <span class="comment">//默认 HashMap 集合初始容量为16（必须是 2 的倍数）</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">4</span>; <span class="comment">// aka 16</span></span><br><span class="line">   <span class="comment">//集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>;</span><br><span class="line">   <span class="comment">//默认的填充因子</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="number">0.75f</span>;</span><br><span class="line">   <span class="comment">//当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>;</span><br><span class="line">   <span class="comment">//当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>;</span><br><span class="line">   <span class="comment">/**(JDK1.8新增)</span></span><br><span class="line"><span class="comment">    * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，</span></span><br><span class="line"><span class="comment">    * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="number">64</span>;</span><br></pre></td></tr></table></figure>

<p><strong>注意：后面三个字段是 JDK1.8 新增的，主要是用来进行红黑树和链表的互相转换。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 初始化使用，长度总是 2的幂</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;K,V&gt;[] table;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 保存缓存的entrySet（）</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 此映射中包含的键值映射的数量。（集合存储键值对的数量）</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数</span></span><br><span class="line"><span class="comment">     * 主要用于迭代器中的快速失败</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> modCount;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 调整大小的下一个大小值（容量*加载因子）。capacity * load factor</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">int</span> threshold;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 散列表的加载因子。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">final</span> <span class="keyword">float</span> loadFactor;</span><br></pre></td></tr></table></figure>

<p>下面我们重点介绍上面几个字段：</p>
<p><strong>①、Node&lt;K,V&gt;[] table</strong></p>
<p>HashMap是有数组+链表+红黑树组成，<strong>这里的数组就是table字段</strong>。后面对其进行<strong>初始化长度默认是</strong> <code>DEFAULT_INITIAL_CAPACITY= 16</code>。</p>
<p>而且jdk声明数组长度总是2的n次方（<strong>一定是合数</strong>：<em>合数</em>是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。）。</p>
<p>为什么这里要求是合数，一般我们知道<strong>哈希算法为了避免冲突都要求长度是质数</strong>，这里要求是合数。下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。</p>
<p><strong>②、size</strong></p>
<p>集合中存放key-value 的<strong>数组大小</strong>。</p>
<p><strong>③、loadFactor</strong></p>
<p>装载因子，是用来衡量HashMap满的程度。计算HashMap的实时装载因子的方法为：size/capacity。而不是用占用桶的数量去除以capacity，capacity是桶的数量，也就是table的长度length。</p>
<p><strong>默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议不要修改。</strong></p>
<p>除非在时间和空间都比较特殊的情况下，如果内存空间很多而对时间效率的要求很高，可以降低loadFactor的值；相反，如果内存空间紧张同时又对时间效率要求不高，可以增加loadFactor的值，这个值可以大于1。</p>
<p><strong>④、threshold</strong></p>
<p>计算公式：capacity * loadFactor 。</p>
<p>这个值是当前已经数组长度的最大值。超过这个数目就要进行resize(扩容)。扩容后的HashMap容量是之前容量的两倍。</p>
<h2 id="5-构造函数"><a href="#5-构造函数" class="headerlink" title="5. 构造函数"></a>5. 构造函数</h2><p><strong>①、默认无参构造函数</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 默认构造函数，初始化加载因子loadFactor = 0.75</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR; </span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>无参构造器，初始化散列表的加载因子为0.75</p>
<p><strong>②、指定初始容量的构造函数</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> initialCapacity 指定初始化容量</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> loadFactor 加载因子 0.75</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//初始化容量不能小于 0 ，否则抛出异常</span></span><br><span class="line">        <span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal initial capacity: "</span> +</span><br><span class="line">                                               initialCapacity);</span><br><span class="line">        <span class="comment">//如果初始化容量大于2的30次方，则初始化容量都为2的30次方</span></span><br><span class="line">        <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">            initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">        <span class="comment">//如果加载因子小于0，或者加载因子是一个非数值，抛出异常</span></span><br><span class="line">        <span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal load factor: "</span> +</span><br><span class="line">                                               loadFactor);</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line">        <span class="keyword">this</span>.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回大于等于initialCapacity的最小的二次幂数值。</span></span><br><span class="line">    <span class="comment">// &gt;&gt;&gt; 操作符表示无符号右移，高位取0。</span></span><br><span class="line">    <span class="comment">// | 按位或运算</span></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">tableSizeFor</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = cap - <span class="number">1</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">        <span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>



<h2 id="6-确定哈希桶数组索引位置"><a href="#6-确定哈希桶数组索引位置" class="headerlink" title="6. 确定哈希桶数组索引位置"></a>6. 确定哈希桶数组索引位置</h2><p>前面讲解哈希表的时候，我们知道是用散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。</p>
<p>HashMap 是数组+链表+红黑树的组合，我们希望在<strong>有限个数组位置的时候</strong>，尽量没有位置的元素只有一个，<strong>那么当我们用散列函数求得索引位置的时候，能马上知道对应位置的元素是不是我们想要的，而不是进行链表的遍历或者红黑树的遍历</strong>。这会大大优化我们的查询效率。</p>
<p>看一下HashMap中的hash算法：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> h;</span><br><span class="line">    <span class="comment">// &gt;&gt;&gt;表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0</span></span><br><span class="line">        <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    i = (table.length - <span class="number">1</span>) &amp; hash;<span class="comment">//这一步是在后面添加元素putVal()方法中进行位置的确定</span></span><br></pre></td></tr></table></figure>



<p>主要分为三步：</p>
<ol>
<li>取HashCode的值：key.hashCode()</li>
<li>高位参与运算：h&gt;&gt;&gt;16</li>
<li>取模运算：(n-1) &amp; hash</li>
</ol>
<p>这里获取 hashCode() 方法的值是变量，但是我们知道，对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。</p>
<p>为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，<strong>取模运算相对开销还是很大的</strong>，那该如何优化呢？</p>
<p>HashMap使用的方法很巧妙，<strong>它通过hash&amp;(table.length-1)来得到该对象的保存位</strong>，前面说过HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。</p>
<p><strong>当length总是2的n次方的时候，hash &amp; (length-1)运算等价于对 length 取模，也就是hash%length。但是&amp;比%具有更高的效率。比如 n % 32 = n &amp; (32 -1)</strong></p>
<p><strong>这也解释了为什么要保证数组的长度总是2的n次方。</strong></p>
<p>再就是在JDK1.8中还有个高位参与运算，hashCode()得到的是一个32位的int类型的值，通过hashCode()的高16位 <strong>异或</strong> 低16位实现的：(h = k.hashCode()) ^ (h &gt;&gt;&gt; 16)，主要是从速度，功效，质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低bit都参数Hash的计算中，同时不会有太大的开销。</p>
<p>下面举例说明：n为table的长度：</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200420/100924560.png" alt="mark"></p>
<h2 id="7-添加元素"><a href="#7-添加元素" class="headerlink" title="7. 添加元素"></a>7. 添加元素</h2><p><strong>JDK1.8中put方法：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//hash(key)就是上面讲的hash方法，对其进行了第一步和第二步处理</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> hash 索引的位置</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key  键</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value  值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> onlyIfAbsent true 表示不要更改现有值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> evict false表示table处于创建模式</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">            <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">         Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">         <span class="comment">//如果table为null或者长度为0，则进行初始化</span></span><br><span class="line">         <span class="comment">//resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法</span></span><br><span class="line">         <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">             n = (tab = resize()).length;</span><br><span class="line">         <span class="comment">//注意：这里用到了前面讲解获得key的hash码的第三步，取模运算，下面的if-else分别是 tab[i] 为null和不为null</span></span><br><span class="line">         <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">             tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);<span class="comment">//tab[i] 为null，直接将新的key-value插入到计算的索引i位置</span></span><br><span class="line">         <span class="keyword">else</span> &#123;<span class="comment">//tab[i] 不为null，表示该位置已经有值了</span></span><br><span class="line">             Node&lt;K,V&gt; e; K k;</span><br><span class="line">             <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">                 ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                 e = p;<span class="comment">//节点key已经有值了，直接用新值覆盖</span></span><br><span class="line">             <span class="comment">//该链是红黑树</span></span><br><span class="line">             <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                 e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">             <span class="comment">//该链是链表</span></span><br><span class="line">             <span class="keyword">else</span> &#123;</span><br><span class="line">                 <span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                     <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                         p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                         <span class="comment">//链表长度大于8，转换成红黑树</span></span><br><span class="line">                         <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                             treeifyBin(tab, hash);</span><br><span class="line">                         <span class="keyword">break</span>;</span><br><span class="line">                     &#125;</span><br><span class="line">                     <span class="comment">//key已经存在直接覆盖value</span></span><br><span class="line">                     <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                         ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                         <span class="keyword">break</span>;</span><br><span class="line">                     p = e;</span><br><span class="line">                 &#125;</span><br><span class="line">             &#125;</span><br><span class="line">             <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">                 V oldValue = e.value;</span><br><span class="line">                 <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                     e.value = value;</span><br><span class="line">                 afterNodeAccess(e);</span><br><span class="line">                 <span class="keyword">return</span> oldValue;</span><br><span class="line">             &#125;</span><br><span class="line">         &#125;</span><br><span class="line">         ++modCount;<span class="comment">//用作修改和新增快速失败</span></span><br><span class="line">         <span class="keyword">if</span> (++size &gt; threshold)<span class="comment">//超过最大容量，进行扩容</span></span><br><span class="line">             resize();</span><br><span class="line">         afterNodeInsertion(evict);</span><br><span class="line">         <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<ol>
<li><p>判断键值对数组table是否为空或者为null,否则执行resize()进行扩容或进行空间分配；</p>
</li>
<li><p>根据键值对key计算hash值得到插入的数组索引i,如果table[i] == null，直接就在新建节点添加；<strong>转下下面的6</strong>,如果talbe[i] 不为空，<strong>转向3</strong></p>
</li>
<li><p>判断talbe[i]的首个元素是否和key一样，如果相同直接覆盖value，<strong>否则转向4</strong>，这里的相同指的是hashcode以及equals。</p>
</li>
<li><p>判断table[i]是否是treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，<strong>否则转向5</strong></p>
</li>
<li><p>遍历table[i]，判断链表长度是否大于8，大于8的话就把链表转换成红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可。</p>
</li>
<li><p>插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，则进行扩容。</p>
</li>
<li><p>如果新插入的key不存在，则返回null,如果新插入的key存在，则返回原key对应的value值（注意新插入的value会覆盖原来的value值）</p>
</li>
</ol>
<p><strong>注意1：看第58，59行代码：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (++size &gt; threshold)<span class="comment">//超过最大容量，进行扩容</span></span><br><span class="line">    resize();</span><br></pre></td></tr></table></figure>

<p>这里有个考点，我们知道 HashMap 是由数组+链表+红黑树（JDK1.8）组成，如果在添加元素的时候，发生冲突，会将冲突的数放在链表上，当链表长度超过8时。会自动转换成红黑树。</p>
<p>那么有如下问题：<strong>数组上有5个元素，而某个链表上有3个元素，问此HashMap的 size 是多大？</strong></p>
<p>我们分析第58,59 行代码，很容易知道，<strong>只要是调用put()方法添加元素，那么就会调用++size（这里有个例外是插入重复的key的键值对，不会调用，但是重复的key元素不会影响到size）</strong></p>
<p><strong>所以，上面的答案是7</strong></p>
<p><strong>注意2：看第 53 、 60 行代码：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">afterNodeAccess(e);</span><br><span class="line">afterNodeInsertion(evict);</span><br></pre></td></tr></table></figure>

<p>这里调用的该方法，其实是调用了如下实现方法：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">afterNodeAccess</span><span class="params">(Node&lt;K,V&gt; p)</span> </span>&#123; &#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">afterNodeInsertion</span><span class="params">(<span class="keyword">boolean</span> evict)</span> </span>&#123; &#125;</span><br></pre></td></tr></table></figure>

<p>　　这都是一个<strong>空的方法实现</strong>，我们在这里可以不用管，但是在后面<strong>介绍 LinkedHashMap 会用到</strong>，LinkedHashMap 是继承的 HashMap，并且重写了该方法，后面我们会详细介绍。</p>
<h2 id="8-扩容机制"><a href="#8-扩容机制" class="headerlink" title="8. 扩容机制"></a>8. 扩容机制</h2><p>扩容（resize），我们知道集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，<strong>如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor），这里的threshold不是数组的最大长度。</strong></p>
<p>那么必须扩大数组的长度，Java中的数组都是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组。就好比以前用的事小桶装水，现在小桶装不下了，使用一个更大的桶。</p>
<ul>
<li>JDK1.8融入了红黑树的机制，比较复杂，这里我们<strong>先介绍 JDK1.7的扩容源码</strong>，便于理解，然后在介绍JDK1.8的源码。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//参数 newCapacity 为新数组的大小</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">resize</span><span class="params">(<span class="keyword">int</span> newCapacity)</span> </span>&#123;</span><br><span class="line">        Entry[] oldTable = table;<span class="comment">//引用扩容前的 Entry 数组</span></span><br><span class="line">        <span class="keyword">int</span> oldCapacity = oldTable.length;</span><br><span class="line">        <span class="keyword">if</span> (oldCapacity == MAXIMUM_CAPACITY) &#123;<span class="comment">//扩容前的数组大小如果已经达到最大(2^30)了</span></span><br><span class="line">            threshold = Integer.MAX_VALUE;<span class="comment">///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了</span></span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        Entry[] newTable = <span class="keyword">new</span> Entry[newCapacity];<span class="comment">//初始化一个新的Entry数组</span></span><br><span class="line">        transfer(newTable, initHashSeedAsNeeded(newCapacity));<span class="comment">//将数组元素转移到新数组里面</span></span><br><span class="line">        table = newTable;</span><br><span class="line">        threshold = (<span class="keyword">int</span>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + <span class="number">1</span>);<span class="comment">//修改阈值</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">transfer</span><span class="params">(Entry[] newTable, <span class="keyword">boolean</span> rehash)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> newCapacity = newTable.length;</span><br><span class="line">        <span class="keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;<span class="comment">//遍历数组</span></span><br><span class="line">            <span class="keyword">while</span>(<span class="keyword">null</span> != e) &#123;</span><br><span class="line">                Entry&lt;K,V&gt; next = e.next;</span><br><span class="line">                <span class="keyword">if</span> (rehash) &#123;</span><br><span class="line">                    e.hash = <span class="keyword">null</span> == e.key ? <span class="number">0</span> : hash(e.key);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">int</span> i = indexFor(e.hash, newCapacity);<span class="comment">//重新计算每个元素在数组中的索引位置</span></span><br><span class="line">                e.next = newTable[i];<span class="comment">//标记下一个元素，添加是链表头添加</span></span><br><span class="line">                newTable[i] = e;<span class="comment">//将元素放在链上</span></span><br><span class="line">                e = next;<span class="comment">//访问下一个 Entry 链上的元素</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>通过方法我们可以看到，JDK1.7中首先是创建一个新的大容量的数组，然后依次重新计算原集合所有元素的索引，然后重新赋值。</p>
<p>如果数组某个位置产生了<strong>hash冲突，使用的是单链表的头插入方式，同一个位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。</strong></p>
<p><strong>下面我们在看看JDK1.8的。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Initializes or doubles table size.  If null, allocates in</span></span><br><span class="line"><span class="comment"> * accord with initial capacity target held in field threshold.</span></span><br><span class="line"><span class="comment"> * Otherwise, because we are using power-of-two expansion, the</span></span><br><span class="line"><span class="comment"> * elements from each bin must either stay at same index, or move</span></span><br><span class="line"><span class="comment"> * with a power of two offset in the new table.</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the table</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">    Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line">    <span class="comment">// 原数组如果为null，则长度赋值0</span></span><br><span class="line">    <span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length;</span><br><span class="line">    <span class="keyword">int</span> oldThr = threshold;</span><br><span class="line">    <span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 如果原数组长度大于0</span></span><br><span class="line">    <span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 数组大小如果已经大于等于最大值(2^30)</span></span><br><span class="line">        <span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">            <span class="comment">// 修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了</span></span><br><span class="line">            threshold = Integer.MAX_VALUE;</span><br><span class="line">            <span class="keyword">return</span> oldTab;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">            <span class="comment">// 阈值扩大一倍</span></span><br><span class="line">            newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// double threshold</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 旧阈值大于0，则将新容量直接等于旧的阈值 </span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) <span class="comment">// initial capacity was placed in threshold</span></span><br><span class="line">        newCap = oldThr;</span><br><span class="line">    <span class="comment">// 阈值等于0，oldCap也等于0（集合未进行初始化）</span></span><br><span class="line">    <span class="keyword">else</span> &#123;               <span class="comment">// zero initial threshold signifies using defaults</span></span><br><span class="line">        <span class="comment">// 数组长度初始化为16</span></span><br><span class="line">        newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">        <span class="comment">// 阈值等于16*0.75 = 12 </span></span><br><span class="line">        newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 计算新阈值的上限</span></span><br><span class="line">    <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor;</span><br><span class="line">        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                  (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">    &#125;</span><br><span class="line">    threshold = newThr;</span><br><span class="line">    <span class="meta">@SuppressWarnings</span>(&#123;<span class="string">"rawtypes"</span>,<span class="string">"unchecked"</span>&#125;)</span><br><span class="line">        Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">    table = newTab;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 如果原数组不为空</span></span><br><span class="line">    <span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 把每个bucket都移动到新的buckets中</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">            Node&lt;K,V&gt; e;</span><br><span class="line">            <span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="comment">// 元数据j位置变为null,便于垃圾回收</span></span><br><span class="line">                oldTab[j] = <span class="keyword">null</span>;</span><br><span class="line">                <span class="comment">// 数组没有下一个引用（不是链表）</span></span><br><span class="line">                <span class="keyword">if</span> (e.next == <span class="keyword">null</span>)</span><br><span class="line">                    newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">                <span class="comment">// 红黑树</span></span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    ((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line">                <span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">                    Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">                    Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">                    Node&lt;K,V&gt; next;</span><br><span class="line">                    <span class="keyword">do</span> &#123;</span><br><span class="line">                        next = e.next;</span><br><span class="line">                        <span class="comment">// 原索引</span></span><br><span class="line">                        <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                            <span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">                                loHead = e;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                loTail.next = e;</span><br><span class="line">                            loTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="comment">// 原索引+oldCap</span></span><br><span class="line">                        <span class="keyword">else</span> &#123;</span><br><span class="line">                            <span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">                                hiHead = e;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                hiTail.next = e;</span><br><span class="line">                            hiTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">                    <span class="comment">// 原索引放到bucket里</span></span><br><span class="line">                    <span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        loTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        newTab[j] = loHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="comment">// 原索引+oldCap放到bucket里</span></span><br><span class="line">                    <span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        newTab[j + oldCap] = hiHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newTab;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>该访问分为两部分，首先是计算新桶数组的容量newCap和新阈值newThr，然后将原集合的元素重新映射到新集合中。</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200420/205101975.png" alt="mark"></p>
<p>相比较于JDK1.7,  JDK1.8使用的是2次幂扩展（指长度扩展为原来的两倍）。所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。</p>
<p>在扩充HashMap的时候，不需要像JDK1.7那样重新计算hash值，只需要看看原来的hash值新增的那个bit是1还是0就好了，如果是0的话索引不变，是1的话索引变成“原索引+oldCap”。</p>
<h2 id="9-删除元素"><a href="#9-删除元素" class="headerlink" title="9. 删除元素"></a>9. 删除元素</h2><p>HashMap删除元素首先是要找到桶的位置，然后如果是链表，则进行链表遍历。找到需要删除的元素后，进行删除。</p>
<p>如果是红黑树，也就是进行树的遍历，找到元素删除后，进行平衡调节。需要注意的是，当红黑树的节点小于6的时候，会自动转换成链表。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Removes the mapping for the specified key from this map if present.</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  key key whose mapping is to be removed from the map</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or</span></span><br><span class="line"><span class="comment"> *         &lt;tt&gt;null&lt;/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;.</span></span><br><span class="line"><span class="comment"> *         (A &lt;tt&gt;null&lt;/tt&gt; return can also indicate that the map</span></span><br><span class="line"><span class="comment"> *         previously associated &lt;tt&gt;null&lt;/tt&gt; with &lt;tt&gt;key&lt;/tt&gt;.)</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">remove</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="keyword">return</span> (e = removeNode(hash(key), key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>)) == <span class="keyword">null</span> ?</span><br><span class="line">        <span class="keyword">null</span> : e.value;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Implements Map.remove and related methods</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> hash hash for key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key the key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> value the value to match if matchValue, else ignored</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> matchValue if true only remove if value is equal</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> movable if false do not move other nodes while removing</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the node, or null if none</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">removeNode</span><span class="params">(<span class="keyword">int</span> hash, Object key, Object value,</span></span></span><br><span class="line"><span class="function"><span class="params">                           <span class="keyword">boolean</span> matchValue, <span class="keyword">boolean</span> movable)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, index;</span><br><span class="line">    <span class="comment">// (n - 1) &amp; hash找到桶的位置</span></span><br><span class="line">    <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">        (p = tab[index = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">        Node&lt;K,V&gt; node = <span class="keyword">null</span>, e; K k; V v;</span><br><span class="line">        <span class="comment">// 如果键的值与链表的第一个节点相等，则将node指向该节点</span></span><br><span class="line">        <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">            ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            node = p;</span><br><span class="line">        <span class="comment">// 如果桶节点存在下一个节点</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((e = p.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">// 红黑树</span></span><br><span class="line">            <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                <span class="comment">//找到需要删除的红黑树节点</span></span><br><span class="line">                node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);</span><br><span class="line">            <span class="comment">// 是链表的话，遍历链表，找到待删除的节点</span></span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key ||</span><br><span class="line">                         (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                        node = e;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    p = e;</span><br><span class="line">                &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 删除节点，并进行调节红黑树平衡</span></span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span> &amp;&amp; (!matchValue || (v = node.value) == value ||</span><br><span class="line">                             (value != <span class="keyword">null</span> &amp;&amp; value.equals(v)))) &#123;</span><br><span class="line">            <span class="comment">// 红黑树</span></span><br><span class="line">            <span class="keyword">if</span> (node <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                ((TreeNode&lt;K,V&gt;)node).removeTreeNode(<span class="keyword">this</span>, tab, movable);</span><br><span class="line">            <span class="comment">// 链表</span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (node == p)</span><br><span class="line">                tab[index] = node.next;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                p.next = node.next;</span><br><span class="line">            ++modCount;</span><br><span class="line">            --size;</span><br><span class="line">            afterNodeRemoval(node);</span><br><span class="line">            <span class="keyword">return</span> node;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>注意第 46 行代码：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">afterNodeRemoval(node);</span><br></pre></td></tr></table></figure>

<p>这也是为实现 LinkedHashMap 做准备的，<strong>在这里和上面一样，是一个空方法实现</strong>，可以不用管。而在 LinkedHashMap 中进行了重写，用来维护删除节点后，链表的前后关系。</p>
<h2 id="10-查找元素"><a href="#10-查找元素" class="headerlink" title="10. 查找元素"></a>10. 查找元素</h2><p>①、通过 key 查找 value</p>
<p>首先通过key找到计算索引，找到桶位置。</p>
<p>先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回null。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? <span class="keyword">null</span> : e.value;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Implements Map.get and related methods</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> hash hash for key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key the key</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the node, or null if none</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> hash, Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="keyword">int</span> n; K k;</span><br><span class="line">    <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">        (first = tab[(n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 根据key计算的索引  检查第一个索引</span></span><br><span class="line">        <span class="keyword">if</span> (first.hash == hash &amp;&amp; <span class="comment">// always check first node</span></span><br><span class="line">            ((k = first.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            <span class="keyword">return</span> first;</span><br><span class="line">        <span class="comment">// 不是第一个节点</span></span><br><span class="line">        <span class="keyword">if</span> ((e = first.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">// 遍历树进行查找</span></span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                <span class="keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">            <span class="comment">// 遍历链表进行查找</span></span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">return</span> e;</span><br><span class="line">            &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>②、判断是否存在给定的 key 或者 value</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">   <span class="comment">/**</span></span><br><span class="line"><span class="comment">    * Returns &lt;tt&gt;true&lt;/tt&gt; if this map contains a mapping for the</span></span><br><span class="line"><span class="comment">    * specified key.</span></span><br><span class="line"><span class="comment">    *</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span>   key   The key whose presence in this map is to be tested</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@return</span> &lt;tt&gt;true&lt;/tt&gt; if this map contains a mapping for the specified</span></span><br><span class="line"><span class="comment">    * key.</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 根据key来吵着</span></span><br><span class="line">   <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsKey</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">return</span> getNode(hash(key), key) != <span class="keyword">null</span>;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">   <span class="comment">/**</span></span><br><span class="line"><span class="comment">    * Returns &lt;tt&gt;true&lt;/tt&gt; if this map maps one or more keys to the</span></span><br><span class="line"><span class="comment">    * specified value.</span></span><br><span class="line"><span class="comment">    *</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> value value whose presence in this map is to be tested</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@return</span> &lt;tt&gt;true&lt;/tt&gt; if this map maps one or more keys to the</span></span><br><span class="line"><span class="comment">    *         specified value</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsValue</span><span class="params">(Object value)</span> </span>&#123;</span><br><span class="line">       Node&lt;K,V&gt;[] tab; V v;</span><br><span class="line">       <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; size &gt; <span class="number">0</span>) &#123;</span><br><span class="line">           <span class="comment">//   遍历桶</span></span><br><span class="line">           <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">               <span class="comment">//  遍历桶的每个节点的元素</span></span><br><span class="line">               <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next) &#123;</span><br><span class="line">                   <span class="keyword">if</span> ((v = e.value) == value ||</span><br><span class="line">                       (value != <span class="keyword">null</span> &amp;&amp; value.equals(v)))</span><br><span class="line">                       <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>



<h2 id="11-遍历元素"><a href="#11-遍历元素" class="headerlink" title="11. 遍历元素"></a>11. 遍历元素</h2><p>首先构造一个 HashMap 集合：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">HashMap&lt;String, Object&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">map.put(<span class="string">"A"</span>,<span class="string">"1"</span>);</span><br><span class="line">map.put(<span class="string">"B"</span>,<span class="string">"2"</span>);</span><br><span class="line">map.put(<span class="string">"C"</span>,<span class="string">"3"</span>);</span><br></pre></td></tr></table></figure>

<p>①、分别获取 key 集合和 value 集合。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//1、分别获取key和value的集合</span></span><br><span class="line"><span class="keyword">for</span>(String key : map.keySet())&#123;</span><br><span class="line">    System.out.println(key);</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">for</span>(Object value : map.values())&#123;</span><br><span class="line">    System.out.println(value);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>②、获取 key 集合，然后遍历key集合，根据key分别得到相应value</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 2. 获取key集合，然后遍历key集合，根据key分别得到相应的value</span></span><br><span class="line">Set&lt;String&gt; keySet = map.keySet();</span><br><span class="line"><span class="keyword">for</span> (Object str : keySet) &#123;</span><br><span class="line">    System.out.println(str + <span class="string">"-&gt;"</span> + map.get(str));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>③、<strong>得到 Entry 集合，然后遍历 Entry</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 3. 得到Entry集合，然后遍历Entry</span></span><br><span class="line">Set&lt;Map.Entry&lt;String, Object&gt;&gt; entrySet = map.entrySet();</span><br><span class="line"><span class="keyword">for</span> (Map.Entry&lt;String, Object&gt; entry : entrySet) &#123;</span><br><span class="line">    System.out.println(entry.getKey() + <span class="string">"--&gt;"</span> + entry.getValue());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>④、迭代</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 4. 迭代</span></span><br><span class="line">Iterator&lt;Map.Entry&lt;String, Object&gt;&gt; iterator = map.entrySet().iterator();</span><br><span class="line"><span class="keyword">while</span> (iterator.hasNext())&#123;</span><br><span class="line">    Map.Entry&lt;String, Object&gt; mapEntry = iterator.next();</span><br><span class="line">    System.out.println(mapEntry.getKey()+ <span class="string">"--&gt;"</span> + mapEntry.getValue());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>基本上使用第三种方法的性能是最好的</strong></p>
<p>第一种遍历方法我们只需要key集合或者只需要value集合时候使用</p>
<p>第二种遍历方法效率太低，不用就行</p>
<p>第四种效率也还行，关键是在遍历的过程中我们可以对元素进行删除。</p>
<h2 id="12-总结"><a href="#12-总结" class="headerlink" title="12. 总结"></a>12. 总结</h2><p><strong>Java7 HashMap的问题：</strong></p>
<ol>
<li><p>并发环境下的死锁</p>
</li>
<li><p>可以通过精心构造的恶意请求引发Dos攻击</p>
</li>
</ol>
<p>HashMap总结：</p>
<p>①、基于JDK1.8的HashMap是由数组+链表+红黑树组成，当链表长度超过 8 时会自动转换成红黑树，当红黑树节点个数小于 6 时，又会转化成链表。相对于早期版本的 JDK HashMap 实现，新增了红黑树作为底层数据结构，在数据量较大且哈希碰撞较多时，能够极大的增加检索的效率。</p>
<p>②、允许 key 和 value 都为 null。key 重复会被覆盖，value 允许重复。</p>
<p>③、非线程安全</p>
<p>④、无序（遍历HashMap得到元素的顺序不是按照插入的顺序）</p>
<p>参考链接：</p>
<p><a href="https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#" target="_blank" rel="noopener">https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#</a></p>
<p><a href="https://www.cnblogs.com/ysocean/p/8711071.html" target="_blank" rel="noopener">https://www.cnblogs.com/ysocean/p/8711071.html</a></p>
<p><a href="https://www.cnblogs.com/nullllun/p/8327664.html" target="_blank" rel="noopener">https://www.cnblogs.com/nullllun/p/8327664.html</a></p>
<h2 id="13-HashMap-死循环"><a href="#13-HashMap-死循环" class="headerlink" title="13. HashMap 死循环"></a>13. HashMap 死循环</h2><p><strong>参考博客</strong>：<a href="https://www.jianshu.com/p/1e9cf0ac07f4" target="_blank" rel="noopener">https://www.jianshu.com/p/1e9cf0ac07f4</a></p>
<ul>
<li>HashMap 在并发使用的时候可能发生死循环，导致cpu100%</li>
<li><strong>如果是在单线程下使用HashMap，自然是没有问题的</strong>，如果后期由于代码优化，这段逻辑引入了多线程并发执行<ul>
<li><strong>在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，会惊讶的发现，线程都则赛在hashMap 的 get() 方法上，服务器重启之后，问题消失，过段时间又出来了。</strong></li>
<li>这是为什么？</li>
</ul>
</li>
</ul>
<p><strong>原因分析</strong></p>
<ol>
<li>在内部，hashMap 使用一个 Entry 数组保存key value, 当一对key value 被加入的时候，会通过hashmap的寻址算法得到数组下标index,算法很简单，根据key的hash值，对数组的大小取模 <code>hash &amp; (table.length - 1)</code>,并把结果插入数组的对应位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。</li>
<li>如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。</li>
<li>当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash.</li>
</ol>
<p><strong>举例分析</strong></p>
<ul>
<li>假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1.</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">transfer</span><span class="params">(Entry[] newTable, <span class="keyword">boolean</span> rehash)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> newCapacity = newTable.length;</span><br><span class="line">    <span class="keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;</span><br><span class="line">        <span class="keyword">while</span>(<span class="keyword">null</span> != e) &#123;</span><br><span class="line">            Entry&lt;K,V&gt; next = e.next;</span><br><span class="line">            <span class="keyword">if</span> (rehash) &#123;</span><br><span class="line">                e.hash = <span class="keyword">null</span> == e.key ? <span class="number">0</span> : hash(e.key);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">int</span> i = indexFor(e.hash, newCapacity);</span><br><span class="line">            e.next = newTable[i];</span><br><span class="line">            newTable[i] = e;</span><br><span class="line">            e = next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>以下是节点移动的相关逻辑。</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164114218.png" alt="mark"></p>
<ul>
<li>插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组。</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164146437.png" alt="mark"></p>
<ol>
<li>假设 <strong>线程2</strong> 在执行到<code>Entry&lt;K,V&gt; next = e.next;</code>之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。</li>
<li><strong>线程1</strong>继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点</li>
<li>第一步，移动节点a </li>
<li>第二步，移动节点b</li>
<li>注意，这里的顺序是反过来的，继续移动节点c</li>
</ol>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164301683.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164306846.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164311468.png" alt="mark"></p>
<ol start="6">
<li><p>这个时候 <strong>线程1</strong> 的时间片用完，内部的table还没有设置成新的newTable， <strong>线程2</strong> 开始执行，这时内部的引用关系如下：</p>
</li>
<li><p>这时，在 <strong>线程2</strong> 中，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。</p>
</li>
</ol>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164455306.png" alt="mark"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Entry&lt;K,V&gt; next = e.next;</span><br><span class="line"><span class="keyword">int</span> i = indexFor(e.hash, newCapacity);</span><br><span class="line">e.next = newTable[i];</span><br><span class="line">newTable[i] = e;</span><br><span class="line">e = next;</span><br></pre></td></tr></table></figure>

<p>执行之后的引用关系如下图</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164523603.png" alt="mark"></p>
<ol start="9">
<li>执行后，变量e指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系</li>
</ol>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164613761.png" alt="mark"></p>
<p>变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：<br> 1、执行完<code>Entry&lt;K,V&gt; next = e.next;</code>，目前节点a没有next，所以变量next指向null；<br> 2、<code>e.next = newTable[i];</code> 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；<br> 3、<code>newTable[i] = e</code> 把节点a放到了数组i位置；<br> 4、<code>e = next;</code> 把变量e赋值为null，因为第一步中变量next就是指向null；</p>
<p>所以最终的引用关系是这样的：</p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200728-164736862.png" alt="mark"></p>
<p><strong>节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。</strong></p>
<p><strong>另外，如果线程2把newTable设置成到内部的table，节点c的数据就丢了，看来还有数据遗失的问题。</strong></p>
<p>所以在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。</p>

      
      <!-- reward -->
      
      <div id="reward-btn">
        打赏
      </div>
      
    </div>
      <!-- copyright -->
      
        <div class="declare">
          <ul class="post-copyright">
            <li>
              <i class="ri-copyright-line"></i>
              <strong>版权声明： </strong s>
              本博客所有文章除特别声明外，均采用 <a href="https://www.apache.org/licenses/LICENSE-2.0.html" rel="external nofollow"
                target="_blank">Apache License 2.0</a> 许可协议。转载请注明出处！
            </li>
          </ul>
        </div>
        
    <footer class="article-footer">
      
          
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=http://zhuuu.work/2020/05/03/jdk_SourceCode/JDK1.8-07-HashMap/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/JDK%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" rel="tag">JDK源码分析</a></li></ul>


    </footer>

  </div>

  
  
  <nav class="article-nav">
    
      <a href="/2020/05/03/jdk_SourceCode/JDK1.8-08-HashSet/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            JDK1.8源码-08-java.util.HashSet
          
        </div>
      </a>
    
    
      <a href="/2020/05/02/JUC/JUC-13-%E5%BC%82%E6%AD%A5%E5%9B%9E%E8%B0%83/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">JUC-13-异步回调</div>
      </a>
    
  </nav>


  

  
  
<!-- valine评论 -->
<div id="vcomments-box">
    <div id="vcomments">
    </div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='https://cdn.jsdelivr.net/npm/valine@1.3.10/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        notify: false,
        verify: '',
        app_id: '',
        app_key: '',
        path: window.location.pathname,
        avatar: 'mp',
        placeholder: '给我的文章加点评论吧~',
        recordIP: true
    });
    const infoEle = document.querySelector('#vcomments .info');
    if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
        infoEle.childNodes.forEach(function (item) {
            item.parentNode.removeChild(item);
        });
    }
</script>
<style>
    #vcomments-box {
        padding: 5px 30px;
    }

    @media screen and (max-width: 800px) {
        #vcomments-box {
            padding: 5px 0px;
        }
    }

    #vcomments-box #vcomments {
        background-color: #fff;
    }

    .v .vlist .vcard .vh {
        padding-right: 20px;
    }

    .v .vlist .vcard {
        padding-left: 10px;
    }
</style>

  

  
  
<div class="gitalk" id="gitalk-container"></div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.css">


<script src="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.js"></script>


<script src="https://cdn.jsdelivr.net/npm/blueimp-md5@2.10.0/js/md5.min.js"></script>

<script type="text/javascript">
  var gitalk = new Gitalk({
    clientID: 'db188ed8c86dc4b0dbf3',
    clientSecret: 'a58f92160e5a9efd726b7d533000a0737f3e3f3e',
    repo: 'Blog-comments',
    owner: 'Zhuuuuuuuu',
    admin: ['Zhuuuuuuuu'],
    // id: location.pathname,      // Ensure uniqueness and length less than 50
    id: md5(location.pathname),
    distractionFreeMode: false,  // Facebook-like distraction free mode
    pagerDirection: 'last'
  })

  gitalk.render('gitalk-container')
</script>

  

</article>
</section>
      <footer class="footer">
  <div class="outer">
    <ul class="list-inline">
      <li>
        &copy;
        2019-2021
        Zhuuu
      </li>
      <li>
        
      </li>
    </ul>
    <ul class="list-inline">
      <li>
        
        
        <span>
  <i>PV:<span id="busuanzi_value_page_pv"></span></i>
  <i>UV:<span id="busuanzi_value_site_uv"></span></i>
</span>
        
      </li>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s9.cnzz.com/z_stat.php?id=1278069914&amp;web_id=1278069914'></script>
        
      </li>
    </ul>
  </div>
</footer>
    <div class="to_top">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>
      </div>
    </main>
      <aside class="sidebar">
        <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="朱酱酱的学习博客"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">主页</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">标签</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JVM/">JVM</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JDK%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/">JDK源码</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/">多线程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Mysql/">Mysql</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Redis/">Redis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E8%AE%BE%E8%AE%A1%E8%80%85%E6%A8%A1%E5%BC%8F/">设计模式</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/MyBatis/">MyBatis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringMVC/">SpringMVC</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Spring/">Spring</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringBoot/">SpringBoot</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">Linux</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Leetcode/">Leetcode</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%89%8D%E7%AB%AF/">前端</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B/">网络编程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/photoshop/">photoshop</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="http://smartzhuuu.lofter.com/" target="_blank" rel="noopener">摄影</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/about">关于我</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="Search">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
      </aside>
      <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯咖啡吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
      
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/jquery.justifiedGallery.min.js"></script>


<script src="/js/lazyload.min.js"></script>


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<script src="/js/share.js"></script>



<script src="/fancybox/jquery.fancybox.min.js"></script>




<script>
  try {
    var typed = new Typed("#subtitle", {
    strings: ['昨夜西风凋碧树。独上高楼，望尽天涯路','衣带渐宽终不悔，为伊消得人憔悴。','众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。'],
    startDelay: 0,
    typeSpeed: 200,
    loop: true,
    backSpeed: 100,
    showCursor: true
    });
  } catch (err) {
  }
  
</script>




<script src="/js/tocbot.min.js"></script>

<script>
  // Tocbot_v4.7.0  http://tscanlin.github.io/tocbot/
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer:'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto',
    onClick: (e) => {
      $('.toc-link').removeClass('is-active-link');
      $(`a[href=${e.target.hash}]`).addClass('is-active-link');
      $(e.target.hash).scrollIntoView();
      return false;
    }
  });
</script>


<script>
  var ayerConfig = {
    mathjax: true
  }
</script>


<script src="/js/ayer.js"></script>


<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>



<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


<script type="text/javascript" src="https://js.users.51.la/20544303.js"></script>
  </div>
</body>

</html>